package levelorder;

import entity.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class FindMaxInEachLine {
    /*
    * 515. 在每个树行中找最大值
    * 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
    *
    * 二叉树的节点个数的范围是 [0,10^4]
    * -2^31 <= Node.val <= 2^31 - 1
    * */
    public static void main(String[] args){

    }

    // 我的想法：
    public List<Integer> mySolution(TreeNode root){
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            Integer max = Integer.MIN_VALUE;
            while (len > 0){
                TreeNode node = deque.pop();
                max = max > node.val? max : node.val;
                if(node.left != null) deque.add(node.left);
                if(node.right != null) deque.add(node.right);
                len--;
            }
            res.add(max);
        }
        return res;
    }
}
